Algoritmo de Euclides estendido

En aritmética e programación informática, o algoritmo de Euclides estendido é unha extensión do algoritmo de Euclides que calcula, alén do máximo común divisor (mcd) dos números enteiros a e b, tamén os coeficientes da identidade de Bézout, que son números enteiros x e y tal que

ax+by=\gcd(a,b)

.

E sendo $a$ e $b$ positivos, un de $x$ ou $y$ é negativo.

O algoritmo de Euclides estendido é particularmente útil cando a e b son coprimos. Con esa condición temos que x é o inverso multiplicativo modular de a módulo b, e y é o inverso multiplicativo modular de b módulo a.

Do mesmo xeito, o algoritmo de Euclides polinómico estendido permite calcular o inverso multiplicativo en extensións de corpos alxébricos e, en particular, en corpos finitos de orde non prima.

Cun algoritmo moi similar podemos calcular o máximo común divisor polinómico e os coeficientes da identidade de Bézout de dous polinomios dunha variable.

Descrición

O algoritmo de Euclides estándar son unha sucesión de divisións cuxos cocientes non se utilizan. Só se usan os restos. Para o algoritmo estendido tamén fan falta os sucesivos cocientes.

{\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-c_{i}r_{i}&{\text{e }}0&\leq r_{i+1}<|r_{i}|&{\text{(isto define }}c_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-c_{i}s_{i}\\t_{i+1}&=t_{i-1}-c_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}

O algoritmo de Euclides estendido procede de xeito similar, mais engade outras dúas secuencias $s_{i},t_{i}$ , sendo $c_{i}$ os cocientes e $r_{i}$ os restos como segue:

O cálculo tamén se detén cando $r_{k+1}=0$ e dá

$r_{k}$ é o máximo común divisor da entrada $a=r_{0}$ e $b=r_{1}.$
Os coeficientes de Bézout son $s_{k}$ e $t_{k},$ é dicir $\gcd(a,b)=r_{k}=as_{k}+bt_{k}$
Os cocientes de a e b polo seu máximo común divisor veñen dados por $s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}$ e $t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}$

A maiores, se a e b son ambos os dous positivos e $\gcd(a,b)\neq \min(a,b)$ , daquela

|s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{e}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor

para $0\leq i\leq k,$ onde $\lfloor x\rfloor$ denota a parte enteira de $x$ , é dicir, o maior enteiro non maior que $x$ .

Isto implica que o par de coeficientes de Bézout proporcionado polo algoritmo de Euclides estendido é o par mínimo de coeficientes de Bézout, xa que é o único par que satisfai ambas as desigualdades anteriores.

A continuación un exemplo pode clarificar.

Exemplo

A seguinte táboa mostra como funciona o algoritmo de Euclides estendido coas entradas 240 e 46^[1]. O máximo común divisor é a última entrada distinta de cero, 2 na columna "resto". O cálculo detense na fila 6, porque o resto é 0. Os coeficientes de Bézout aparecen nas dúas últimas entradas da penúltima fila. De feito, é doado verificar que -9 $\cdot$ 240 + 47 $\cdot$ 46 = 2. Finalmente, as dúas últimas entradas 23 e 120 da última fila son, ata o signo, os cocientes da entrada 46 e 240 polo máximo común divisor 2.

índice i	cociente c_i−1	Resto r_i	s_i	t_i
0		240	1	0
1		46	0	1
2	240 ÷ 46 = 5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10 = 4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
4	10 ÷ 6 = 1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4 = 1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2 = 2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

A maiores, os cocientes, en azul, son os coeficientes da fracción continua de 240/46 = [5, 4, 1, 1, 2].

Algoritmo polinómico de Euclides estendido

Para polinomios dunha variable con coeficientes nun corpo, todo funciona de xeito similar, división euclidiana, identidade de Bézout e algoritmo de Euclides estendido. A primeira diferenza é que, na división de Euclides e no algoritmo, a desigualdade $0\leq r_{i+1}<|r_{i}|$ ten que ser substituída por unha desigualdade nos graos do polinomio $\deg r_{i+1}<\deg r_{i}.$ Para o demais, todo o que precede neste artigo segue sendo o mesmo, simplemente substituíndo os enteiros por polinomios.

Unha segunda diferenza reside no límite do tamaño dos coeficientes de Bézout proporcionados polo algoritmo, que é máis preciso no caso polinómico, o que leva ao seguinte teorema.

En matemáticas, é común esixir que o máximo común divisor sexa un polinomio mónico. Para conseguir isto, abonda con dividir cada elemento da saída polo coeficiente principal de $r_{k}.$ Isto permite que, se a e b son coprimos, se obtén 1 no lado dereito da desigualdade de Bézout. En caso contrario, pódese obter calquera constante distinta de cero.

Se a e b son dous polinomios distintos de cero, entón o algoritmo de Euclides estendido produce o único par de polinomios (s, t) tal que

as+bt=\gcd(a,b)

O algoritmo de Euclides estendido é a ferramenta esencial para calcular inversos multiplicativos en estruturas modulares, normalmente os enteiros modulares e as extensións de corpos alxébricos. Un exemplo notable deste último caso son os corpos finitos de orde non prima.

\deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).

Unha terceira diferenza é que, no caso polinómico, o máximo común divisor defínese só ata a multiplicación por unha constante distinta de cero. Hai varias formas de definir sen ambigüidades un máximo común divisor.

\gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),

Cálculo de inversos multiplicativos en aritmética modular

Números enteiros modulares

Un elemento $a$ do anel $Z / n Z$ ten un inverso multiplicativo (é dicir, é unha unidade) se é coprimo con $n$ . En particular, se $n$ é primo, $a$ ten un inverso multiplicativo se non é cero (módulo $n$ ). Así, $Z / n Z$ é un corpo se e só se $n$ é primo.

A identidade de Bézout afirma que $a$ e $n$ son primos primos se e só se existen números enteiros $s$ e $t$ tal que

ns+at=1

Reducindo esta identidade módulo $n$ dáse

at\equiv 1\mod n.

Así $t$ , ou, máis exactamente, o resto da división de $t$ por $n$ , é o inverso multiplicativo de $a$ módulo $n$ .

Extensións simples de corpos alxébricos

Exemplo

Por exemplo, se o polinomio usado para definir o corpo finito GF(2⁸) é $p = x 8 + x 4 + x 3 + x + 1$ , e $a = x 6 + x 4 + x + 1$ é o elemento cuxo inverso se desexa, entón a realización do algoritmo dá como resultado o cálculo descrito na seguinte táboa embaixo. Lembremos que en corpos de orde 2ⁿ, un ten − z = z e z + z = 0 para cada elemento z do corpo). Temos que 1 é o único elemento distinto de cero en GF(2).

paso	cociente	r	s	t
		$p = x 8 + x 4 + x 3 + x + 1$	1	0
		$a = x 6 + x 4 + x + 1$	0	1
1	$x 2 + 1$	$x 2 = p - a (x 2 + 1)$	1	$x 2 + 1 = 0 - 1 \cdot (x 2 + 1)$
2	$x 4 + x 2$	$x + 1 = a - x 2 (x 4 + x 2)$	$x 4 + x 2 = 0 - 1(x 4 + x 2)$	$x 6 + x 2 + 1 = 1 - (x 4 + x 2) (x 2 + 1)$
3	$x + 1$	$1 = x 2 - (x + 1) (x + 1)$	$x 5 + x 4 + x 3 + x 2 +1 = 1 - (x +1)(x 4 + x 2)$	$x 7 + x 6 + x 3 + x = (x 2 + 1) - (x + 1) (x 6 + x 2 + 1)$
4	$x + 1$	$0 = (x + 1) - 1 \times (x + 1)$	$x 6 + x 4 + x + 1 = (x 4 + x 2) - (x +1)(x 5 + x 4 + x 3 + x 2 +1)$

Así, o inverso é $x 7 + x 6 + x 3 + x$ , como se pode confirmar multiplicando os dous elementos xuntos e tomando o resto por $p$ do resultado.

O caso de máis de dous números

Pódese manexar o caso de máis de dous números de forma iterativa.

\gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n}))),\dots ),

Notas

↑ "The Extended Euclidean Algorithm".

Véxase tamén

Bibliografía

Knuth, Donald. The Art of Computer Programming. Addison-Wesley. Volume 2, Chapter 4.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

Outros artigos

Ligazóns externas

Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)

[1] "The Extended Euclidean Algorithm".

[1]